// Copyright 2016 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_COMPILER_LOOP_VARIABLE_OPTIMIZER_H_
#define V8_COMPILER_LOOP_VARIABLE_OPTIMIZER_H_

#include "src/compiler/functional-list.h"
#include "src/compiler/node-aux-data.h"
#include "src/zone/zone-containers.h"

namespace v8 {
namespace internal {
    namespace compiler {

        class CommonOperatorBuilder;
        class Graph;
        class Node;

        class InductionVariable : public ZoneObject {
        public:
            Node* phi() const { return phi_; }
            Node* effect_phi() const { return effect_phi_; }
            Node* arith() const { return arith_; }
            Node* increment() const { return increment_; }
            Node* init_value() const { return init_value_; }

            enum ConstraintKind { kStrict,
                kNonStrict };
            enum ArithmeticType { kAddition,
                kSubtraction };
            struct Bound {
                Bound(Node* bound, ConstraintKind kind)
                    : bound(bound)
                    , kind(kind)
                {
                }

                Node* bound;
                ConstraintKind kind;
            };

            const ZoneVector<Bound>& lower_bounds() { return lower_bounds_; }
            const ZoneVector<Bound>& upper_bounds() { return upper_bounds_; }

            ArithmeticType Type() { return arithmeticType_; }

        private:
            friend class LoopVariableOptimizer;

            InductionVariable(Node* phi, Node* effect_phi, Node* arith, Node* increment,
                Node* init_value, Zone* zone, ArithmeticType arithmeticType)
                : phi_(phi)
                , effect_phi_(effect_phi)
                , arith_(arith)
                , increment_(increment)
                , init_value_(init_value)
                , lower_bounds_(zone)
                , upper_bounds_(zone)
                , arithmeticType_(arithmeticType)
            {
            }

            void AddUpperBound(Node* bound, ConstraintKind kind);
            void AddLowerBound(Node* bound, ConstraintKind kind);

            Node* phi_;
            Node* effect_phi_;
            Node* arith_;
            Node* increment_;
            Node* init_value_;
            ZoneVector<Bound> lower_bounds_;
            ZoneVector<Bound> upper_bounds_;
            ArithmeticType arithmeticType_;
        };

        class LoopVariableOptimizer {
        public:
            void Run();

            LoopVariableOptimizer(Graph* graph, CommonOperatorBuilder* common,
                Zone* zone);

            const ZoneMap<int, InductionVariable*>& induction_variables()
            {
                return induction_vars_;
            }

            void ChangeToInductionVariablePhis();
            void ChangeToPhisAndInsertGuards();

        private:
            const int kAssumedLoopEntryIndex = 0;
            const int kFirstBackedge = 1;

            struct Constraint {
                Node* left;
                InductionVariable::ConstraintKind kind;
                Node* right;

                bool operator!=(const Constraint& other) const
                {
                    return left != other.left || kind != other.kind || right != other.right;
                }
            };

            using VariableLimits = FunctionalList<Constraint>;

            void VisitBackedge(Node* from, Node* loop);
            void VisitNode(Node* node);
            void VisitMerge(Node* node);
            void VisitLoop(Node* node);
            void VisitIf(Node* node, bool polarity);
            void VisitStart(Node* node);
            void VisitLoopExit(Node* node);
            void VisitOtherControl(Node* node);

            void AddCmpToLimits(VariableLimits* limits, Node* node,
                InductionVariable::ConstraintKind kind, bool polarity);

            void TakeConditionsFromFirstControl(Node* node);
            const InductionVariable* FindInductionVariable(Node* node);
            InductionVariable* TryGetInductionVariable(Node* phi);
            void DetectInductionVariables(Node* loop);

            Graph* graph() { return graph_; }
            CommonOperatorBuilder* common() { return common_; }
            Zone* zone() { return zone_; }

            Graph* graph_;
            CommonOperatorBuilder* common_;
            Zone* zone_;
            NodeAuxData<VariableLimits> limits_;
            NodeAuxData<bool> reduced_;

            ZoneMap<int, InductionVariable*> induction_vars_;
        };

    } // namespace compiler
} // namespace internal
} // namespace v8

#endif // V8_COMPILER_LOOP_VARIABLE_OPTIMIZER_H_
